package arithmetic.LeetCode;

/**
 * @author jiangfeng 2019/8/18 23:28
 * 一个大数字符 移调k个数后最小
 *
 * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
 *
 * 注意:
 *
 * num 的长度小于 10002 且 ≥ k。
 * num 不会包含任何前导零。
 * 示例 1 :
 *
 * 输入: num = "1432219", k = 3
 * 输出: "1219"
 * 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
 *
 *
 * https://leetcode-cn.com/problems/remove-k-digits/description/
 */
public class removeKdigital {

    /**
     * 方法1： 贪心算法， result迭代
     * 思路2 ： 用栈。 比栈顶元素大时就把栈顶弹出。
     * @param num
     * @param k
     * @return
     */

    public static String removeKdigits(String num, int k) {
        if(num.length()==k) return "0";
        String result = num;
        int i = 0;
        while (i < k) {
            int j = 1;
            boolean isSub = false;//是否找到最大数
            while (j < result.length()) {
                if (result.charAt(j - 1) > result.charAt(j)) {
                    int index = j;
                    if(j==1){ // 避免删去后第一个是0
                        while (index < result.length() && result.charAt(index) == '0') index++;
                        if (index == result.length()) {//后面都是0就不用继续判断了 直接是0
                            return "0";
                        }
                    }
                    result = result.substring(0, j - 1) + result.substring(index);
                    isSub = true;
                    break;
                }
                j++;
            }
            if (!isSub) {// 避免最大数是最后一个
                result = result.substring(0, j - 1);
            }
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
       /* String a= "1232143321";
        System.out.println(a.substring(0,1));
        System.out.println(a.substring(1,a.length()));*/
       //char[] a = {'1',null,'2'};
       //String.valueOf(a);

       // System.out.println(  removeKdigits("1432219", 3));
      //  System.out.println(  removeKdigits("112",1));
        System.out.println(  removeKdigits("1107", 1));
    }
}
